package LeetCode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class LC_515_FindLargestValueinEachTreeRow {

    public static void main(String[] args) {

    }

    public class Solution {
        public List<Integer> largestValues(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>();
            List<Integer> res = new LinkedList<>();
            if (root == null) return res;
            queue.offer(root);
            while (!queue.isEmpty()) {
                int levelNum = queue.size();
                int temp = queue.peek().val;
                if (queue.peek().left != null) queue.offer(queue.peek().left);
                if (queue.peek().right != null) queue.offer(queue.peek().right);
                queue.poll();
                for (int i = 1; i < levelNum; i++) {
                    if (queue.peek().val > temp) temp = queue.peek().val;
                    if (queue.peek().left != null) queue.offer(queue.peek().left);
                    if (queue.peek().right != null) queue.offer(queue.peek().right);
                    queue.poll();
                }
                res.add(temp);
            }
            return res;
        }
    }

    public class Solution_2 {
        public List<Integer> largestValues(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            helper(root, res, 0);
            return res;
        }

        private void helper(TreeNode root, List<Integer> res, int d) {
            if (root == null) return;
            if (d == res.size())
                res.add(root.val);
            else
                res.set(d, Math.max(res.get(d), root.val));
            helper(root.left, res, d + 1);
            helper(root.right, res, d + 1);
        }

    }
}